package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM13 判断一个链表是否为回文结构</a>
 *
 * @author c2b
 * @since 2024/3/14 11:34
 */
public class BM13IsPail {
    public static class Solution {
        public boolean isPail(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            // 先找出中点
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 反转后半段
            ListNode currNode = slow.next;
            ListNode prevNode = null;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            while (prevNode != null) {
                if (prevNode.val != head.val) {
                    return false;
                }
                prevNode = prevNode.next;
                head = head.next;
            }
            return true;
        }
    }
}
